package com.uhu.code;

import com.uhu.code.help.TreeNode;

import java.util.*;

/**
 * todo
 */
public class Solution437 {

    public static void main(String[] args) {
        Solution437 solution437 = new Solution437();
        TreeNode treeNode = new TreeNode(10);
        treeNode.left = new TreeNode(5);
        treeNode.left.left = new TreeNode(3);
        treeNode.left.left.left = new TreeNode(3);
        treeNode.left.left.right = new TreeNode(-2);
        treeNode.left.right = new TreeNode(2);
        treeNode.left.right.right = new TreeNode(1);
        treeNode.right = new TreeNode(-3);
        treeNode.right.right = new TreeNode(11);

        System.out.println(solution437.pathSum(treeNode, 8));
    }

    public int pathSum(TreeNode root, int targetSum) {
        Stack<TreeNode> stk = new Stack<>();
        Set<String> sSet = new HashSet<>();
        while(!stk.isEmpty() || root != null) {
            while(root != null) {
                stk.push(root);
                root = root.left;
            }
            TreeNode node = stk.peek();
            if(node == null) {
                stk.pop();
                stk.pop();
            }else {
                if (node.left == null && node.right == null) {
                    // 是叶子节点 开始添加路径
                    getPath(stk, targetSum, sSet);
                }
                if (node.right != null) {
                    stk.push(null);
                    stk.push(node.right);
                    root = node.right.left;
                } else {
                    stk.pop();
                }
            }
        }
        return sSet.size();
    }

    private void getPath(Stack<TreeNode> stk, int targetSum, Set<String> sSet) {
        List<TreeNode> tempList = new ArrayList<>();
        Stack<TreeNode> tempStk = new Stack<>();
        tempStk.addAll(stk);
        while(!tempStk.isEmpty()) {
            if(tempStk.peek() == null) {
                tempStk.pop();
            }else {
                tempList.add(tempStk.pop());
            }
        }
        for(int i = 0; i <= tempList.size() - 1; i++) {
            for(int j = i + 1; j <= tempList.size(); j++) {
                int temp = 0;
                String nodeStr = "";
                int start = i;
                int end = j;
                while (start < end) {
                    temp += tempList.get(start).val;
                    nodeStr += tempList.get(start);
                    if (temp == targetSum) {
                        sSet.add(nodeStr);
                    }
                    start ++;
                }
            }
        }
    }
}
